package leetcode;

/**
 * @Description 1310. 子数组异或查询
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.5.12
 */

public class T1310 {
    public static void main(String[] args) {
        T1310 t1310 = new T1310();
        int[] arr = {1, 3, 4, 8};
        int[][] queries = {{0, 1}, {1, 2},{0,3},{3,3}};
        t1310.xorQueries(arr, queries);
    }


    /**
     * 暴力解法
     *
     * @param arr
     * @param queries
     * @return
     */
    public int[] xorQueries1(int[] arr, int[][] queries) {
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];

            int tmp = 0;
            for (int j = l; j <= r; j++) {
                tmp ^= arr[j];
            }
            result[i] = tmp;
        }
        return result;
    }

    /**
     * xors[i] 表示 arr[0]....arr[i] 的所有数异或
     * queries[l,r] = xors[l-1]^ xors[r]
     *
     * @param arr
     * @param queries
     * @return
     */
    public int[] xorQueries(int[] arr, int[][] queries) {
        int[] result = new int[queries.length];
        int[] xors = new int[arr.length + 1];

        xors[0] = 0;
        for (int i = 0; i < arr.length; i++) {
            xors[i + 1] = xors[i] ^ arr[i];
        }
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0] ;
            l = l < 0 ? 0 : l;
            int r = queries[i][1] +1;
            if (l == r) {
                result[i] = arr[i];
                continue;
            }
            result[i] = xors[l] ^ xors[r];
        }

        return result;
    }
}
